package lookas.test;

import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Permutation {

    private static final int INIT_CAPACITY = 100;
    private Integer[]        perm;

    public Permutation() {
        this.perm = new Integer[INIT_CAPACITY];
    }

    public Permutation(int size) {
        this.perm = new Integer[size];
    }

    public Permutation(Integer[] perm) {
        this.perm = perm;
    }

    public void put(Integer x, Integer y) {
        ensureCapacity(x + 1);
        perm[x] = y;
    }

    private void trimToSize() {
        int i = perm.length;
        int n = 0;// TODO
        while (i > 0 && perm[--i] == null)
            n++;
        n = perm.length - n;
        if (perm.length > n) {
            Object[] oldData = perm;
            perm = new Integer[n];
            System.arraycopy(oldData, 0, perm, 0, n);
        }
    }

    private void ensureCapacity(int size) {
        if (perm.length < size) {
            Object[] oldData = perm;
            perm = new Integer[size];
            System.arraycopy(oldData, 0, perm, 0, oldData.length);
        }
    }

    public List<List<Integer>> asCycles() {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        List<Integer> licznik = new LinkedList<Integer>();
        LinkedList<Integer> tmp;
        for (int i = 0; i < perm.length; i++) {
            licznik.add(i);
        }

        while (licznik.size() > 0) {
            tmp = new LinkedList<Integer>();
            Integer n = licznik.remove(0);
            tmp.add(n);
            while (!tmp.contains(this.image(n))) {
                n = this.image(n);
                tmp.add(n);
                licznik.remove(n);
            }
            if (tmp.size() > 1)
                ret.add(tmp);

        }
        return ret;
    }

    public Integer image(int n) {
        Integer x = n;
        try {
            x = perm[n] != null ? perm[n] : n;
        } catch (Exception e) {
        }
        return x;
    }

    public static Permutation fromCycles(int size, List<List<Integer>> cycles) {
        Permutation p = new Permutation(size);
        for (List<Integer> list : cycles) {
            int next, prev, first, i = 0;
            next = prev = first = list.get(0);
            while (list.size() > i) {
                next = list.get(i++);
                p.put(prev, next);
                prev = next;
            }
            p.put(next, first);
        }
        p.trimToSize();
        return p;
    }

    public static Permutation fromCycles(List<List<Integer>> cycles) {
        return fromCycles(INIT_CAPACITY, cycles);
    }

    public Permutation multiply(Permutation p) {
        int size = perm.length > p.perm.length ? perm.length : p.perm.length;
        Permutation ret = new Permutation(size);
        for (int i = 0; i < size; i++) {
            ret.put(i, p.image(this.image(i)));
        }
        return ret;
    }

    public static Permutation fromString(String s) {
        Permutation p = new Permutation();
        Matcher matcher = Pattern.compile("\\d+").matcher(s);
        int i = 1;
        while (matcher.find())
            p.put(i++, Integer.valueOf(matcher.group()));
        p.trimToSize();
        return p;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder("[");
        if (perm != null) {
            for (int i = 1; i < perm.length; i++) {
                Integer n = perm[i];
                if (n != null)
                    s.append(n);
                else
                    s.append(i);
                s.append(",");
            }
            if (s.length() > 1)
                s.setLength(s.length() - 1);
        }
        s.append("]");
        return s.toString();
    }
}
